//K个⼀组翻转链表
//https://leetcode.cn/problems/reverse-nodes-in-k-group/description/
public class Test {
    public static void main(String[] args) {
        //
    }
}

//Definition for singly-linked list.
class ListNode {
    int val;
    ListNode next;
    ListNode() {}
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}

class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        //判断需要逆序多少组
        ListNode cur = head;
        int n = 0;
        while(cur!=null){//计算链表元素个数
            n++;
            cur = cur.next;
        }
        n = n/k;//此时，n表示需要重排序的组数
        cur = head;//表示每个将要被放到ret的节点
        ListNode prev = new ListNode();//下一组重排序放置的起点
        ListNode ret = new ListNode(0);//总的头结点
        ListNode tmp = null;//表示每个新加入后的节点
        //ret.next = head;
        prev = ret;
        ListNode prevHead = ret;
        while(n>0){//一组一组进行重排序
            for(int i = 0; i < k; i++){
                if(i == 0) prevHead = cur;
                tmp = cur;
                cur = cur.next;
                tmp.next = prev.next;
                prev.next = tmp;

            }
            prev = prevHead;

            n--;
        }

        //处理没有构成一组的剩余节点
        while(cur!=null){
            prev.next = cur;
            prev = cur;
            cur = cur.next;
        }
        return ret.next;
    }

}